package 链表.带头单链表;

/**
 * 带头(虚拟头节点)单链表
 */
public class Lin_ked_List_With_Head {
    //有效节点的个数
    private int size;
    //创建一个虚拟头节点
    // 实实在在存在的Node对象，不存储数据，就作为火车头
    private Node dummyHead = new Node();

    //头插add
    public void addFirst(int val){

        //第三种更加简便的，运用的是 之前学的 动态初始化的简写，语法糖
        dummyHead.next = new Node(val, dummyHead.next);//创建出一个新节点
        size++;

        //第二种，简化后的
        /*
        Node newNode = new Node(val, dummyHead.next);//创建出一个新节点
        dummyHead.next = newNode;
        size++;
         */

        //第一种写法
        /*
        Node newNode = new Node();//创建出一个新节点
        newNode.val = val;//赋值

        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
        size ++;//有效元素 + 1

         */
    }

    /**
     * 在索引为 index 的位置上 插入 一个节点
     * @return
     */
    public void add(int index, int val){
        //对索引判断
        if(index < 0 || index > size){
            System.out.println("插入的索引错误！");
            return;
        }
        Node prve = dummyHead;//始终充当前驱的身份
        //想要让prve成为要插入位置的前驱，就需要知道要走几步
        //作图得知，插入index位置，需要做 index步
        for (int i = 0; i < index; i++) {
            prve = prve.next;
        }//循环后，prve就是前驱的位置了

        //方法1
        //让新节点指向 前驱的 后面的后面一个
        Node node = new Node(val);//要插入的对象
        node.next = prve.next;
        prve.next = node;//前驱指向新节点
        size++;

        //方法2 简便写法，跟之前都一样
        //让新节点指向 前驱的 后面的后面一个
//        prve.next = new Node(val, prve.next);//要插入的对象
//        size++;
    }

    //尾插
    public void addLase(int val){
        //直接调用 我们上一个写的 add插入就行
        add(size , val);
    }


    /**
     * 删除 索引 位置的节点,并返回删除前的节点的val值
     * @return
     */
    public int remove(int index){
        if( rangeCheck(index) ){
            //如果索引合法走这里
            Node prve = dummyHead;

            for (int i = 0; i < index; i++) {
                prve = prve.next;
            }//此时的 prve就是 处于 待删除节点 前驱的位置
            Node node = prve.next;
            prve.next = node.next;
            size--;
            return node.val;
        }
        //索引不合法走这里
        System.out.println("你输入的删除索引不合法！");
        return -1;//不合法我们就返回一个 -1
    }

    /**
     * 删除链表中 所有值为 val 的元素
     */
    public void removeAllValue(int val){
        Node prve = dummyHead;//前驱
        Node node = prve.next;//用来判断是否是待删除节点
        while(node != null){

            if(node.val == val){
                node = node.next;//跳过
                prve.next = node;
                size--;
            }else{
                //当遇到的不是val值时，prve才会 放心的向后走到不是删除的节点上面
                prve = node;
                node = node.next;
            }


        }
    }

    /**
     * 删除链表中第一个值为 val的节点
     */
    public void remoValueOnce(int val){

        int tmp = getByValue(val);
        if( tmp != -1 ){

            remove(tmp);
        }
    }

    /**
     *查找第一个为 val 的 索引值为多少,找不到则返回 -1
     */
    public int getByValue(int val){
        Node prve = dummyHead.next;
        for (int i = 0; prve != null ; i++) {
            if(prve.val == val){
                return i;
            }
            prve = prve.next;
        }

        //如果都没找到，则不存在 返回 -1
        return -1;
    }

    /**
     * 查询链表中 是否包含 val 值
     * @return
     */
    public boolean contains(int val){
        int index = getByValue(val);
        return index != -1;
    }

    /**
     * 查询索引为 index 的元素 val 为多少,
     * @return
     */
    public int get(int index){
        // 1.判断index的合法性
        if( rangeCheck(index) ){
           Node x = dummyHead;
            //索引为 index ，那么走到索引的节点上需要 index + 1 步完成
            for (int i = 0; i < index + 1; i++) {
                x = x.next;
            }
            return x.val;
        }
        //不符合索引要求走到这里
        System.out.println("查询的索引值不合理！");
        return -1;
    }

    /**
     * 修改索引为 index 位置的节点值，改为 newVal
     * 返回修改前的值
     */
    public int set(int index, int newVal){

        if(rangeCheck(index)){

            Node x = dummyHead;
            //索引为 index ，那么走到索引的节点上需要 index + 1 步完成
            for (int i = 0; i < index + 1; i++) {
                x = x.next;
            }//循环后x指向的就是索引位置
            int rep = x.val;//保存待返回的值
            x.val = newVal;
            return rep;
        }
        //到这里说明索引不合理
        System.out.println("输入修改的索引不合理");
        return -1;
    }

    //判断索引是否合格
    private boolean rangeCheck(int index) {
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }

    //模拟完善一下toString函数，打印我们写的链表
    public String toString(){
        String rep = "";
        Node prve = dummyHead.next;//第一个节点位置

        while(prve != null){

            rep += prve.val;
            rep += " -> ";
            prve = prve.next;
        }
        rep += "NULL";//表示走到头了
        return rep;
    }

}

/**
 * 单链表的每个节点-车厢类
 */
class Node{

    int val;//单链表保存的值
    Node next;//保存当前节点的下一个地址
    //构造方法
    //1 当传入一个val值的时候，自动给它赋值
    public Node(int val) {
        this.val = val;
    }
    //2 当传入val值和下一个地址的时候，自动给它赋值
    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
    //3 再弄的无参的，什么都不做
    public Node(){

    }
}